GPUDT: A 2D Delaunay Triangulator using Graphics Hardware (version 1.1)
=======================================================================

Copyright (c) 2009, 2010 School of Computing, National University of Singapore. 
All rights reserved.

Project homepage: http://www.comp.nus.edu.sg/~tants/delaunay.html

If you use GPUDT and you like it or have comments on its usefulness etc., we 
would love to hear from you at <tants@comp.nus.edu.sg>. You may share with us
your experience and any possibilities that we may improve the work/code.

-------------------------------------------------------------------------

GPUDT is a C Library that utilizes graphics hardware to compute exact 
Delaunay triangulation. The result is a triangle mesh, each contain the
index of its 3 vertices and the three neighbor triangles.

References: 
1.  Computing Two-dimensional Delaunay Triangulation Using Graphics Hardware
    G.D. Rong, T.S. Tan, Thanh-Tung Cao and Stephanus
    The 2008 ACM Symposium on Interactive 3D Graphics and Games, 
    15--17 Feb, Redwood City, CA, USA, pp. 89--97. 

2.  Parallel Banding Algorithm to Compute Exact Distance Transform with the GPU
    T.T. Cao, K. Tang, A. Mohamed, and T.S. Tan
    The 2010 ACM Symposium on Interactive 3D Graphics and Games, 19-21 Feb, 
    Washington DC, USA.

3.  Proof of Correctness of the DIgital Delaunay Triangulation Algorithm
    T.T. Cao, H. Edelsbrunner, and T.S. Tan
    Manuscript 2010. 

Remark: The current implementation is an improvement to the algorithm proposed
in the above reference #1. In particular, the (main) algorithm is run completely in GPU
instead of GPU+CPU, and is much faster than reported in the above reference #1. 
An update to the above paper is in preparation and will be posted to the project
webpage in due course. 

1. Requirement
==============
- CUDA Toolkit version 2.0 and above. 
- A GPU capable of running CUDA.

By default, GPUDT performs all floating point computation in Double precision. 
You can also turn on the definition SINGLE_PRECISION (see gpudt.h) to switch 
to Single precision mode. 

To run GPUDT with Double precision, you need a GPU with compute capability
1.3 (NVIDIA GT200 series onward). In Single precision mode, GPUDT only 
require a GPU with compute capability 1.1 (NVIDIA G8xxx series onward, 
except Geforce 8800GTX). 

2. Tested
==========
GPUDT has been tested on NVIDIA Geforce 8800GT, 9600M GT, GTX280 and 
Tesla C1060. 

3. In this folder
=================
The following files are included in this distribution:
	
	readme.txt		The file you're reading now
	gpudt.c			The main CPU code of GPUDT
	gpudt.h			Header file, include some configurations, 
					instructions, and some useful macro. 
	*.cu			CUDA source codes
	

The distribution include a sample Visual Studio 2008 project using
GPUDT to compute Delaunay Triangle of a randomly uniformly distributed 
set of 2D points. The triangulation is then drawn using OpenGL, and the 
user can zoom in and move around the triangle mesh. 

Note: When compiling the CUDA code using Double precision, you have to 
enable compute capability 1.3 using the switch -sm_13. If you use 
Single precision, you can use the switch -sm_11. 

4. Acknowledgements
===================
We acknowledge that the code in predicates.h is extracted from the file predicates.c 
obtained from the webpage http://www.cs.cmu.edu/~quake/robust.html. The code in 
cudaCCW.cu is also extracted from the same file, with some minor adjustment to make 
it work in CUDA. 

5. Change logs
+ Version 1.1 (01/25/2010)
   - Replace JFA with PBA for more accurate and faster Discrete Voronoi Diagram computation. 
     Reference: http://www.comp.nus.edu.sg/~tants/pba.html
   - Minor bugs fixed.
+ Version 1.0 (01/03/2009)
   - Initial release


----------------------------------------------------------------------------------
Graphics, Geometry & Games Lab
School of Computing, National University of Singapore
Computing 1
13 Computing Drive
Singapore 117417
Repulic of Singapore
March 2009
----------------------------------------------------------------------------------
Please send bugs and comments to: bug.gpudt@gmail.com  and  tants@comp.nus.edu.sg
